The present invention relates to indoor positioning systems, in particular, improving the indoor positioning accuracy by exploiting invisible Access Points (APs).
Indoor positioning implies to wirelessly locating objects or people inside buildings. Indoor positioning has many applications in the context of commercial, personal, entertainment, health, such as locating a particular store in a mall or finding a conference room inside an office building, etc. Global Positioning System (GPS) is a widely used positioning solution, which is generally not suitable for establishing indoor locations due to signal attenuation caused by building materials and also multi-path propagation caused by surface reflections.
In indoor environments or in the dense urban canyons, where the low level satellite based signals are critically compromised by obscuration and environmental degradation, Wi-Fi based positioning systems are gaming popularity. Wi-Fi hotspots are prevalent in the very areas where GPS starts to straggle and many smart devices are already equipped with Wi-Fi technology that can support positioning applications. Wi-Fi is a mechanism that allows an electronic device to exchange data wirelessly over a computer network. A Wi-Fi enabled device such as a smart phone, a personal computer, a tablet or a video game console can connect to a network resource such as the internet via a wireless network AP. An AP or a hotspot has a range of about 20 meters indoors and a greater range outdoors. Hotspot coverage can comprise an area as small as a single room with walls that block radio signals or as large as many square miles, covered by multiple overlapping APs. A conventional Wi-Fi communication system is explained with the help of FIG. 1.
FIG. 1 illustrates a conventional Wi-Fi communication system 100.
As illustrated in the figure, conventional Wi-Fi communication system 100 includes a user device 102, and an AP database 104. Assuming user device 102 is located at a position (x,y), which needs to be determined. A first AP 106 is located at a position (x1,y1), a second AP 108 is located at a position (x2,y2), a third AP 110 is located at a position (x3,y3) and an i-th AP 112 is located at a position (x1,y1). Assuming the distance between user device 102 and AP 106 is d1, the distance between user device 102 and AP 108 is the distance between user device 102 and AP 110 is and the distance between user device 102 and AP 112 is d1. User device 102 communicates with AP 106-112 via a Wi-Fi communication channel 114 and with AP database 104 via a communication channel 116.
AP database 104 contains the location of APs and is managed by a database vendor such as Google, Navizon and so forth. Generally, a database vendor collects the location of APs by “wardriving” efforts and builds up their database from information collected from multiple users at different times.
Location of user device 102 can be determined based on the locations of AP 106-112. Suppose, user device 102 is a Wi-Fi enabled mobile phone. In one example, user device 102 will scan all APs (for example, AP 106-112) in its vicinity by sending a probe request to all the APs. Typically, an AP will respond with a probe response, which includes the Media Access Control (MAC) address for that AP and some other information regarding the capabilities of that AP. A MAC address is a unique identifier assigned to network interfaces for communications on the physical network segment and will uniquely identify that AP.
User device 102 receives MAC address from AP 106-112 and looks up AP database 104 to get the approximate location of each AP. Once user device 102 has approximate locations for AP 106-112, it can determine its location based on the Receive Signal Strength Indicator (RSSI) for each AP. The received signal, power of an AP may be in terms of dBm (decibels above a reference level of one milliwatt), which indicates how far the AP is from user device 102. For example, if the signal power is really high, it's an indication that AP is really close by. On the other hand, low signal power indicates that the AP is really far away. Based on this information, the approximate location of user device 102 can be easily determined in a conventional Wi-Fi positioning system 100.
The propagation model for Wi-Fi communication channel 114 is usually approximated by the log normal shadowing model. Shadowing is the effect that the received signal power fluctuates due to objects obstructing the propagation path between a transmitter and a receiver. Log normal shadowing model captures effects caused by imperfect antennas and environmental obstruction. Power received from i-th AP 112 in dB can be expressed as:Ri(dB)=αi+10ni log10(d0/di)+w,  (1)where d0 is a reference fixed distance from AP 112 (typically less than 2 m), n is the path loss exponent, αi is the reference power at distance dij and w is a zero-mean white Gaussian noise with variance σ2. The path loss exponent depends on the specific propagation environment and indicates the rate at which the path loss increases with distance.
Given the position of user device 102 as (x,y) and the position of i-th AP 112 as (xi,yi), the distance di is computed as:di=√(x−xi)2+(y−yi)2.  (2)If the different RSSI measurements are independent, the joint distribution is a multivariate Gaussian with a diagonal covariance matrix, i.e., the RSSI measurements are distributed asp(R|x,y)˜N(μ,σi2I).  (3)where R is the Gaussian distribution and μ, is the mean vector withμi=αi+10ni log10(d0/di),  (4)and I is the identity matrix.
The objective of RSSI based indoor positioning is to estimate the position of a user (x,y) from the RSSI measurements (Ri). A typical receiver uses an estimation algorithm, for example, the maximum likelihood estimator to find the most likely position (x,y) that maximizes the probability p of vector R, given x and y, i.e., p(R|x,y).
Conventional Wi-Fi positioning system 100 exploits only visible APs to the receiver each time. If an AP exists in AP database 104 but it does not show up in scanning, a possibility is that the AP is far from the receiver, i.e., the AP is invisible to the receiver. The visible APs usually represent a small percentage of all available APs due to the receiver sensitivity. Receiver sensitivity implies a minimum level of available RF energy (above the background noise level), so that a bit stream can be extracted. Generally, the receivers cannot detect distant APs with very small received powers. However, these APs carry useful information that could be exploited to improve the positioning accuracy.
What is needed is a method for improving the positioning accuracy for RSSI based positioning systems.